package org.chz.utils;

import org.springframework.stereotype.Component;

@Component
public class EditDistanceUtil {
    // 1. 求取一个字符占据的字节数
    public static int nBytesCode(char ch) {
        if ((ch & (1 << 7)) != 0) {
            int nBytes = 1;
            for (int idx = 0; idx != 6; ++idx) {
                if ((ch & (1 << (6 - idx))) != 0) {
                    ++nBytes;
                } else {
                    break;
                }
            }
            return nBytes;
        }
        return 1;
    }

    // 2. 求取一个utf-8字符串的字符长度
    public static int length(String str) {
        int ilen = 0;
        for (int idx = 0; idx < str.length(); ++idx) {
            int nBytes = nBytesCode(str.charAt(idx));
            idx += (nBytes - 1);
            ++ilen;
        }
        return ilen;
    }


    // 3. 中英文通用的最小编辑距离算法
    public static int editDistance(String lhs, String rhs) {
        /*Java默认utf-16，可以直接求长度*/
        int lhs_len = lhs.length();
        int rhs_len = rhs.length();

        int[][] editDist = new int[lhs_len + 1][rhs_len + 1];

        for (int idx = 0; idx <= lhs_len; ++idx) {
            editDist[idx][0] = idx;
        }

        for (int idx = 0; idx <= rhs_len; ++idx) {
            editDist[0][idx] = idx;
        }

        for (int dist_i = 1, lhs_idx = 0; dist_i <= lhs_len; ++dist_i, ++lhs_idx) {
            int nBytes = 1;
//            int nBytes = nBytesCode(lhs.charAt(lhs_idx));

            String sublhs = lhs.substring(lhs_idx, lhs_idx + nBytes);
            lhs_idx += (nBytes - 1);

            for (int dist_j = 1, rhs_idx = 0; dist_j <= rhs_len; ++dist_j, ++rhs_idx) {
//                nBytes = nBytesCode(rhs.charAt(rhs_idx));
                String subrhs = rhs.substring(rhs_idx, rhs_idx + nBytes);
                rhs_idx += (nBytes - 1);

                if (sublhs.equals(subrhs)) {
                    editDist[dist_i][dist_j] = editDist[dist_i - 1][dist_j - 1];
                } else {
                    editDist[dist_i][dist_j] = tripleMin(
                            editDist[dist_i][dist_j - 1] + 1,
                            editDist[dist_i - 1][dist_j] + 1,
                            editDist[dist_i - 1][dist_j - 1] + 1);
                }
            }
        }
        return editDist[lhs_len][rhs_len];
    }

    // 三数取最小值
    private static int tripleMin(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }


    public static void test0() {
        // 字符流的字符串
        String s1 = "abcd"; // 4个字符的字符串
        String s2 = "中国"; // 2个字符的字符串

        String s5 = "abc中国";

        System.out.println("s2与s5的最小编辑距离: " + editDistance(s2, s5));
    }

}
